| 翻訳と辞書 |
| Balinski's theorem ： ウィキペディア英語版 |
Balinski's theorem
In polyhedral combinatorics, a branch of mathematics, Balinski's theorem is a statement about the graph-theoretic structure of three-dimensional polyhedra and higher-dimensional polytopes. It states that, if one forms an undirected graph from the vertices and edges of a convex ''d''-dimensional polyhedron or polytope (its skeleton), then the resulting graph is at least ''d''-vertex-connected: the removal of any ''d'' − 1 vertices leaves a connected subgraph. For instance, for a three-dimensional polyhedron, even if two of its vertices (together with their incident edges) are removed, for any pair of vertices there will still exist a path of vertices and edges connecting the pair.〔.〕
Balinski's theorem is named after mathematician Michel Balinski, who published its proof in 1961,〔.〕 although the three-dimensional case dates back to the earlier part of the 20th century and the discovery of Steinitz's theorem that the graphs of three-dimensional polyhedra are exactly the three-connected planar graphs.〔.〕
==Balinski's proof==
Balinski proves the result based on the correctness of the simplex method for finding the minimum or maximum of a linear function on a convex polytope (the linear programming problem). The simplex method starts at an arbitrary vertex of the polytope and repeatedly moves towards an adjacent vertex that improves the function value; when no improvement can be made, the optimal function value has been reached.
If ''S'' is a set of fewer than ''d'' vertices to be removed from the graph of the polytope, Balinski adds one more vertex ''v''0 to ''S'' and finds a linear function ƒ that has the value zero on the augmented set but is not identically zero on the whole space. Then, any remaining vertex at which ƒ is non-negative (including ''v''0) can be connected by simplex steps to the vertex with the maximum value of ƒ, while any remaining vertex at which ƒ is non-positive (again including ''v''0) can be similarly connected to the vertex with the minimum value of ƒ. Therefore, the entire remaining graph is connected.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Balinski's theorem」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|